package 一和零;

import java.util.Arrays;

/**
 * @author: AirMan
 * @date: 2025/5/9 11:16
 * @description:
 */
public class Solution2 {
    public int findMaxForm(String[] strs, int m, int n) {
        // 重复的子问题：寻找每一个切割的子集中的最大子集长度
        // ① dp数组及其含义：最多有i个0和j个1的strs的最大子集的大小为dp[i][j]
        /*
        物品的重量有了两个维度(下面的解法，如果不好理解的话，就把dp想成是一维的，就很容易和01背包的一维dp对照理解了)
         */
        // ② 动态转移公式：dp[i][j] = Math.max(dp[i][j], dp[i - zeroNum][j - oneNum] + 1);
        //                 能够选取strs[i]的前提：容量足够，且子集的0和1均满足m和n的要求
        // ③ 初始化dp数组：因为物品价值不会是负数，初始为0
        // ④ 遍历顺序：先变量物品，在遍历背包
        // ⑤ 举例推导dp数组:输入：["10","0001","111001","1","0"]，m = 3，n = 3
        //             M/N:   0   1   2   3
        //              0     0   1   1   1
        //              1     1   2   2   2
        //              2     1   2   3   3
        //              3     1   2   3   3


        int[][] dp = new int[m + 1][n + 1];
        for (String str : strs) {
            int zeroSum = 0, oneSum = 0;
            for (char c : str.toCharArray()) {
                if (c == '0') {
                    zeroSum++;
                } else {
                    oneSum++;
                }
            }
            // 遍历背包容量且从后向前遍历！
            for (int i = m; i >= zeroSum; i--) {
                // 0容量的维度
                for (int j = n; j >= oneSum; j--) {
                    // 1容量的维度
                    dp[i][j] = Math.max(dp[i][j], dp[i - zeroSum][j - oneSum] + 1);
                }
            }
            print(dp);
        }
        return dp[m][n];
    }

    private void print(int[][] dp) {
        for (int i = 0; i < dp[0].length; i++) {
            System.out.println(Arrays.toString(dp[i]));
        }
        System.out.println("-------------------");
    }
}
